package second.graph;

import java.util.LinkedList;

public class Solution07 {
    public int numEnclaves(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (grid[0][i] == 1) queue.add(new int[]{0, i});
            if (grid[m - 1][i] == 1) queue.add(new int[]{m - 1, i});
        }
        for (int i = 1; i < m - 1; i++) {
            if (grid[i][0] == 1) queue.add(new int[]{i, 0});
            if (grid[i][n - 1] == 1) queue.add(new int[]{i, n - 1});
        }
        while (!queue.isEmpty()) {
            int[] cur = queue.removeFirst();
            int i = cur[0];
            int j = cur[1];
            grid[i][j] = -1;
            if (i - 1 >= 0 && grid[i - 1][j] == 1) queue.add(new int[]{i - 1, j});
            if (i + 1 < m && grid[i + 1][j] == 1) queue.add(new int[]{i + 1, j});
            if (j - 1 >= 0 && grid[i][j - 1] == 1) queue.add(new int[]{i, j - 1});
            if (j + 1 < n && grid[i][j + 1] == 1) queue.add(new int[]{i, j + 1});
        }
        int res = 0;
        for (int[] ints : grid) {
            for (int j = 0; j < n; j++) {
                if (ints[j] == 1) res++;
            }
        }
        return res;
    }
}

